A convolutional code is a well-known code used for error correction for transmissions in wireless communication systems. In general, an M-tuple of information bits, which are to be encoded by a convolutional encoder, is transformed into an N-tuple of code bits, where M/N is the code rate (N≧M), and the transformation is a function of the last k information bits, where k is the constraint length of the code. The N-tuple of code bits is known as a code word.
FIG. 1 shows schematically an example of a convolutional encoder (for use in a transmitter) with three registers 10,20,30, which are each able to store single bit values, i.e. a “zero” or a “one”. The particular convolutional encoder shown in FIG. 1 successively transforms each bit in the stream of bits to be encoded into a chunk of code bits (in this case comprising two code bits). Once each bit has been encoded, the generated chunks of code bits are joined together in the order in which they were generated to make up a code word for the encoded stream of bits. The first register 10 (the leftmost register in the drawing) is the input bit register, which stores the value of the most recent input bit which is received at input 40 from the stream of bits to be encoded. The second register 20 stores the value of the bit that was input immediately before the most recent input bit, and the third register 30 stores the bit value of the bit that was input immediately before the second most recent input bit. In other words, the register values are bit shifted (to the right) as new input bits arrive. Initially, the second and third registers 20,30 are set to zero, and correspondingly the encoder is said to be in the “state” 00. The values in the second and third registers 20,30 give the “state” of the encoder at any time.
In this example, the bit values stored in the registers 10,20,30 are read from the registers 10,20,30 and are used to calculate two outputs 50,60. The first output 50 is the modulo-2 sum of the input bit stored in the input bit register 10 and the values in the second and third registers 20,30. The convolutional code polynomial for the first output can therefore be written as 1+x+x2. The second output 60 is the modulo-2 sum of the input bit stored in the input bit register 10 and the value in the third register 30. The convolutional code polynomial for the second output can therefore be written as 1+x2. These two outputs 50,60 form a two-bit chunk of a code word. As an example, if the first input bit is a 1, the first output bit 50 will therefore be 1+0+0=1 and the second output bit 60 will be 1+0.1 such that the first two code bits (i.e. the first chunk) of the code word is 11. Each output bit 50,60 is known as a transition bit, and a particular chunk of transition bits is associated with a particular change (or transition) in the state of the encoder caused by the input of a bit. The transition bits 50,60 may sometimes be referred to as parity bits.
The bit in the second register 20 is then written into the third register 30 and the bit in the input bit register 10 is written into the second register 20, thus changing the state of the encoder. In other words, the values in the first and second registers 10,20 are “shifted along” into the second and third registers 20,30 respectively. The second register 20 now stores the value of the first input bit (a 1 in this example). The third register still stores a value of 0. In this example, the state of the encoder thus changes from 00 to 10 due to the input of the first input bit.
Once the chunk of transition bits 50,60 for the first input bit has been generated and the bits in the registers 10,20,30 have been shifted along, the next bit in the data stream is then fed into the input bit register 10. The values from the registers 10,20,30 are then used to calculate the next chunk of transition bits 50,60 and then the value in the input bit register 10 is written into the second register 20, and the value in the second register 20 is written into the third register 30, thus again causing the state of the encoder to change. The second chunk of transition bits 50,60 is associated with the second state change. Following from the previous example, where the first input bit was a 1, the encoder is currently (i.e. before the generation of the second chunk of transition bits) in the state 10. If the second input bit is, for example, another 1, the encoder generates a second chunk of transition bits made up of the two transition bits 1+1+0.0 and 1+0=1, and the state of the encoder changes from the state 10 to 11.
In other examples, the chunks of transition bits 50,60 may be generated using different combinations of the input bit and the register bits (i.e. different convolutional code polynomials). For example, the first transition bit of a chunk of transition bits may instead be the modulo-2 sum of the value in the input bit register 10 and the value in the second register 20. Further, the second transition bit in a chunk of transition bits may instead be the modulo-2 sum of the value in the input bit register 10 and the value in the third register 30.
As an input bit can only ever be a 1 or a 0, a state can only ever change to one of two different states. This can be represented using a trellis diagram, an example of which is illustrated in FIG. 2. In FIG. 2, the first column 70 of the trellis diagram represents the possible states (00, 01, 10, and 11) of an encoder (such as the one shown in FIG. 1) at some time T. The second column 80 represents the possible states of the encoder at the next time instant after a new bit has been fed into the encoder. It can be seen that each state in the first column 70 has two branches diverging from it and leading to one of the two above-mentioned possible states. If the encoder changes from a first state to a second state along a particular branch, a particular chunk of transition bits will be generated. The chunks of transition bits that would be generated by an encoder undergoing a state transition along each branch of the trellis diagram are indicated on the diagram. Following the last example described above, if the encoder changes from state 10 to state 11, the encoder will output the chunk of transition bits 01. The trellis diagram concept is used in receivers of convolutionally encoded bit streams to decode the bit stream and correct for errors. In practice, the trellis diagram is extended to have further state columns with transitions therebetween to represent the successive bits of an m-tuple of information bits that are entered into the encoder and bit shifted through the registers.
In some cases, once an entire code word (comprising a number of chunks of transition bits, each associated with a different input bit) has been generated, it is then simply transmitted wirelessly to be received by a receiver. However, in many transmitters, it is common to scramble the code word before it is transmitted. This helps to prevent the transmitted data from being intercepted. In an example, a code word is scrambled by generating a scrambling sequence and adding successive bits of the scrambling sequence to successive bits of the code word using modulo-2 addition.
Common receivers thus typically receive one or more scrambled code words, which must be descrambled and decoded to output the original information bit streams. This is currently carried out by first descrambling the received code word(s) and then decoding the descrambled code word(s). However, this is relatively power-inefficient.